{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sub Sort LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #array #two-pointers #sorting #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #数组 #双指针 #排序 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subSort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #部分排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组，编写一个函数，找出索引<code>m</code>和<code>n</code>，只要将索引区间<code>[m,n]</code>的元素排好序，整个数组就是有序的。注意：<code>n-m</code>尽量最小，也就是说，找出符合条件的最短序列。函数返回值为<code>[m,n]</code>，若不存在这样的<code>m</code>和<code>n</code>（例如整个数组是有序的），请返回<code>[-1,-1]</code>。</p>\n",
    "<p><strong>示例：</strong></p>\n",
    "<pre><strong>输入：</strong> [1,2,4,7,10,11,7,12,6,7,16,18,19]\n",
    "<strong>输出：</strong> [3,9]\n",
    "</pre>\n",
    "<p><strong>提示：</strong></p>\n",
    "<ul>\n",
    "<li><code>0 <= len(array) <= 1000000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sub-sort-lcci](https://leetcode.cn/problems/sub-sort-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sub-sort-lcci](https://leetcode.cn/problems/sub-sort-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if not array:\n",
    "            return [-1, -1]\n",
    "\n",
    "        # the max value we have seen when iterating from left to right\n",
    "        max_v = -sys.maxsize \n",
    "\n",
    "        # the min value we have seen when interating from right to left\n",
    "        min_v = sys.maxsize\n",
    "\n",
    "        left , right = -1, -1\n",
    "        for i in range(len(array)):\n",
    "            if array[i] < max_v:\n",
    "                right = i\n",
    "            max_v=max(array[i], max_v)\n",
    "\n",
    "        for i in range(len(array)-1 , -1, -1):\n",
    "            if array[i]> min_v:\n",
    "                left = i\n",
    "            min_v = min(min_v, array[i])\n",
    "\n",
    "        if right - left == len(array) - 1:\n",
    "            return [-1, -1]\n",
    "        \n",
    "        return [left, right]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        n = len(array)\n",
    "        start = -1\n",
    "        end = -1\n",
    "        maxVal = -1000000\n",
    "        minVal = 1000000\n",
    "        for i in range(n):\n",
    "            if array[i] < maxVal:\n",
    "                end = i\n",
    "            else:\n",
    "                maxVal = array[i]\n",
    "        for j in range(n-1,-1,-1):\n",
    "            if array[j] > minVal:\n",
    "                start = j\n",
    "            else:\n",
    "                minVal = array[j]\n",
    "        return [start,end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        acc = sorted(array)\n",
    "        n = len(array)\n",
    "        res,left = [],-1\n",
    "        for i in range(n):\n",
    "            if array[i]!=acc[i]:\n",
    "                left = i\n",
    "                break\n",
    "        if left == -1:return [-1,-1]\n",
    "        right = -1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if array[i]!=acc[i]:\n",
    "                right = i\n",
    "                break\n",
    "        return [left,right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        n = len(array)\n",
    "        maxx, minn = -float(\"inf\"), float(\"inf\")\n",
    "        l, r = -1, -1\n",
    "        for i in range(n):\n",
    "            if array[i] < maxx:  # 找到右边居然有值大于max，那么这是右边界\n",
    "                r = i\n",
    "            else:\n",
    "                maxx = array[i]\n",
    "            if array[n - 1 - i] > minn:\n",
    "                l = n - 1 - i\n",
    "            else:\n",
    "                minn = array[n - 1 - i]\n",
    "        return [l, r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if len(array) <= 1:\n",
    "            return [-1, -1]\n",
    "        return self.getSort(array, 0, len(array) - 1)\n",
    "\n",
    "    def getSort(self, array, left, right):\n",
    "        l = -1\n",
    "        r = -1\n",
    "        max_value = array[left]\n",
    "        min_value = array[right]\n",
    "        for i in range(left, right+1):\n",
    "            if array[i] >= max_value:\n",
    "                max_value = array[i]\n",
    "            else:\n",
    "                r = i\n",
    "        if r == -1:\n",
    "            return [-1, -1]\n",
    "        for i in range(right, left-1, -1):\n",
    "            if array[i] <= min_value:\n",
    "                min_value = array[i]\n",
    "            else:\n",
    "                l = i\n",
    "        return [l, r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "            ret = []\n",
    "            max = 0\n",
    "            rightIndex = -1\n",
    "            for index, num in enumerate(array):\n",
    "                if array[index] >= array[max]:\n",
    "                    max = index\n",
    "                else:\n",
    "                    rightIndex = index\n",
    "\n",
    "            min = len(array) - 1\n",
    "            leftIndex = -1\n",
    "            for index in range(len(array) - 2, -1, -1):\n",
    "                if(array[index] <= array[min]):\n",
    "                    min = index\n",
    "                else:\n",
    "                    leftIndex = index\n",
    "            ret.append(leftIndex)\n",
    "            ret.append(rightIndex)\n",
    "\n",
    "            return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        n = len(array)\n",
    "        if n==0:return [-1,-1]\n",
    "        left,flag,acc,minnum = inf,True,[array[0]],array[0]\n",
    "        for i in range(1,n):\n",
    "            if flag and array[i]>=array[i-1]:\n",
    "                minnum = array[i]\n",
    "                acc.append(array[i])\n",
    "                continue\n",
    "            flag = False\n",
    "            if array[i]>minnum:\n",
    "                continue\n",
    "            tmp = bisect.bisect(acc,array[i])\n",
    "            if tmp<left:\n",
    "                minnum = array[i]\n",
    "                left = tmp\n",
    "        \n",
    "        right,flag,acc,maxnum = 0,True,[array[-1]],array[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if flag and array[i]<=array[i+1]:\n",
    "                acc = [array[i]]+acc\n",
    "                maxnum = array[i]\n",
    "                continue\n",
    "            flag = False\n",
    "            if array[i]<maxnum:\n",
    "                continue\n",
    "            tmp = n-(len(acc)-bisect.bisect_left(acc,array[i]))\n",
    "            if tmp>right:\n",
    "                maxnum = array[i]\n",
    "                right = tmp\n",
    "        return [-1,-1] if left==inf else [left,right-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        n = len(array)\n",
    "        if n==0:return [-1,-1]\n",
    "        left,flag,acc,minnum = inf,True,[array[0]],array[0]\n",
    "        for i in range(1,n):\n",
    "            if flag and array[i]>=array[i-1]:\n",
    "                minnum = array[i]\n",
    "                acc.append(array[i])\n",
    "                continue\n",
    "            flag = False\n",
    "            if array[i]>minnum:\n",
    "                continue\n",
    "            tmp = bisect.bisect(acc,array[i])\n",
    "            if tmp<left:\n",
    "                minnum = array[i]\n",
    "                left = tmp\n",
    "        right,flag,acc,maxnum = 0,True,[array[-1]],array[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if flag and array[i]<=array[i+1]:\n",
    "                acc = [array[i]]+acc\n",
    "                maxnum = array[i]\n",
    "                continue\n",
    "            flag = False\n",
    "            if array[i]<maxnum:\n",
    "                continue\n",
    "            tmp = n-(len(acc)-bisect.bisect_left(acc,array[i]))\n",
    "            if tmp>right:\n",
    "                maxnum = array[i]\n",
    "                right = tmp\n",
    "        return [-1,-1] if left==inf else [left,right-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        n = len(array)\n",
    "        if n==0:return [-1,-1]\n",
    "        left,flag,acc,minnum = inf,True,[array[0]],array[0]\n",
    "        for i in range(1,n):\n",
    "            if flag and array[i]>=array[i-1]:\n",
    "                minnum = array[i]\n",
    "                acc.append(array[i])\n",
    "                continue\n",
    "            flag = False\n",
    "            if array[i]>minnum:\n",
    "                continue\n",
    "            tmp = bisect.bisect(acc,array[i])\n",
    "            if tmp<left:\n",
    "                minnum = array[i]\n",
    "                left = tmp\n",
    "        right,flag,acc,maxnum = 0,True,[array[-1]],array[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if flag and array[i]<=array[i+1]:\n",
    "                acc = [array[i]]+acc\n",
    "                maxnum = array[i]\n",
    "                continue\n",
    "            flag = False\n",
    "            if array[i]<maxnum:\n",
    "                continue\n",
    "            tmp = n-(len(acc)-bisect.bisect_left(acc,array[i]))\n",
    "            if tmp>right:\n",
    "                maxnum = array[i]\n",
    "                right = tmp\n",
    "        # print(acc,right,maxnum)\n",
    "        return [-1,-1] if left==inf else [left,right-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subSort(self, array):\n",
    "        \"\"\"\n",
    "        :type array: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if len(array) < 2:\n",
    "            return [-1, -1]\n",
    "        m = 0\n",
    "        flag = True\n",
    "        for i in range(1, len(array)):\n",
    "            if flag and array[i] >= array[m]:\n",
    "                m = i\n",
    "            else:\n",
    "                flag = False\n",
    "                while m > 0 and array[m - 1] > array[i] and m >= 0:\n",
    "                    m -= 1\n",
    "        n = len(array) - 1\n",
    "        flag = True\n",
    "        for i in range(len(array) - 2, -1, -1):\n",
    "            if flag and array[i] <= array[n]:\n",
    "                n = i\n",
    "            else:\n",
    "                flag = False\n",
    "                while n < len(array) - 1 and array[i] > array[n + 1]:\n",
    "                    n += 1\n",
    "        if m >= n:\n",
    "            return [-1, -1]\n",
    "        return [m, n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        n = len(array)\n",
    "        if n==0:return [-1,-1]\n",
    "        left,flag,acc,minnum = inf,True,[array[0]],array[0]\n",
    "        for i in range(1,n):\n",
    "            if flag and array[i]>=array[i-1]:\n",
    "                minnum = array[i]\n",
    "                acc.append(array[i])\n",
    "                continue\n",
    "            flag = False\n",
    "            if array[i]>minnum:\n",
    "                continue\n",
    "            tmp = bisect.bisect(acc,array[i])\n",
    "            if tmp<left:\n",
    "                minnum = array[i]\n",
    "                left = tmp\n",
    "        right,flag,acc,maxnum = 0,True,[array[-1]],array[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if flag and array[i]<=array[i+1]:\n",
    "                acc = [array[i]]+acc\n",
    "                maxnum = array[i]\n",
    "                continue\n",
    "            flag = False\n",
    "            if array[i]<maxnum:\n",
    "                continue\n",
    "            tmp = n-(len(acc)-bisect.bisect_left(acc,array[i]))\n",
    "            if tmp>right:\n",
    "                maxnum = array[i]\n",
    "                right = tmp\n",
    "        # print(acc,right,maxnum)\n",
    "        return [-1,-1] if left==inf else [left,right-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        n = len(array)\n",
    "        if n==0:return [-1,-1]\n",
    "        left,flag,acc,minnum = inf,True,[array[0]],array[0]\n",
    "        for i in range(1,n):\n",
    "            if flag and array[i]>=array[i-1]:\n",
    "                minnum = array[i]\n",
    "                acc.append(array[i])\n",
    "                continue\n",
    "            flag = False\n",
    "            if array[i]>minnum:\n",
    "                continue\n",
    "            tmp = bisect.bisect(acc,array[i])\n",
    "            if tmp<left:\n",
    "                minnum = array[i]\n",
    "                left = tmp\n",
    "        acs = len(acc)\n",
    "        right,flag,acc,maxnum = 0,True,[array[-1]],array[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if i<acs-1:break\n",
    "            if flag and array[i]<=array[i+1]:\n",
    "                acc = [array[i]]+acc\n",
    "                maxnum = array[i]\n",
    "                continue\n",
    "            flag = False\n",
    "            if array[i]<maxnum:\n",
    "                continue\n",
    "            tmp = n-(len(acc)-bisect.bisect_left(acc,array[i]))\n",
    "            if tmp>right:\n",
    "                maxnum = array[i]\n",
    "                right = tmp\n",
    "        return [-1,-1] if left==inf else [left,right-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        nums=sorted(array)\n",
    "        label=[]\n",
    "        if array==nums:\n",
    "            return [-1,-1]\n",
    "        for i in range(len(array)):\n",
    "            if nums[i]-array[i]!=0:\n",
    "                label.append(i)\n",
    "        return [label[0],label[-1]]\n",
    "        \n",
    "        '''题解\n",
    "首先虽然题目没说，但是实际运行下来数列是单调递增的，所以我们下面默认数列是递增的。\n",
    "\n",
    "那么对于元素 a[i] 来说，如果它左边存在大于 a[i] 的元素，那么 a[i] 是一定要参与到排序里去的。或者说如果它右边存在小于 a[i] 的元素，那么 a[i] 也是要参与到排序里去的。\n",
    "\n",
    "所以我们只需要寻找最靠右的那个数（满足左边存在大于它的数），和最靠左的那个数（满足右边存在小于它的数），那么这两个数之间就是要排序的区间了。\n",
    "\n",
    "为什么最靠右的那个（满足左边存在大于它的数）数一定能保证右边没有更小的数了呢？因为如果右边还有更小的数，那么那个更小的数才是更靠右的啊，这就矛盾了。\n",
    "\n",
    "所以我们只需要从左到右扫描一遍，用一个变量维护一下最大值就行了，然后反向再遍历一遍，维护一个最小值。\n",
    "nums=array\n",
    "n=len(nums)\n",
    "max,min=-float('inf'),float('inf')\n",
    "left,right=-1,-1\n",
    "for i in range(n):\n",
    "    if nums[i]<max:#如果该数小于其左边的数，记录下标\n",
    "        right=i\n",
    "    else:\n",
    "        max=nums[i]\n",
    "for j in range(n-1,-1,-1):\n",
    "    if nums[j]>min:\n",
    "        left=j\n",
    "    else:\n",
    "        min=nums[j]\n",
    "print([left,right])\n",
    "'''\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        arraySorted = sorted(array)\n",
    "        for i in range(len(array)):\n",
    "            if array[i]!=arraySorted[i]:\n",
    "                res.append(i)\n",
    "        return [res[0],res[-1]] if res else [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        b  = sorted(array)\n",
    "        ans= []\n",
    "        for i in range(len(b)):\n",
    "            if array[i] != b[i]:ans.append(i)\n",
    "        return [ans[0], ans[-1]] if ans else [-1, -1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        len_array = len(array)\n",
    "        max_array = []\n",
    "        min_array = []\n",
    "        max_num = -float('inf')\n",
    "        min_num = float('inf')\n",
    "        for i in range(len_array):\n",
    "            max_num = max(max_num,array[i])\n",
    "            max_array.append(max_num)\n",
    "            min_num = min(min_num,array[len_array-i-1])\n",
    "            min_array.append(min_num)\n",
    "        res = [-1,-1]\n",
    "        min_array = min_array[::-1]\n",
    "        left,right = 0,len_array-1\n",
    "        while left<right:\n",
    "            if array[left]<=min_array[left]: #小于后面所有的数，正确\n",
    "                left+=1\n",
    "            else:\n",
    "                res[0] = left\n",
    "                if res[0]!=-1 and res[1]!=-1:\n",
    "                    break\n",
    "            if array[right]>=max_array[right]: #大于前面所有的数，正确\n",
    "                right-=1\n",
    "            else:\n",
    "                res[1] = right\n",
    "                if res[0]!=-1 and res[1]!=-1:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if len(array) <= 1:\n",
    "            return [-1, -1]\n",
    "\n",
    "        left_min = [array[0] for _ in range(len(array))]\n",
    "        left_max = [array[0] for _ in range(len(array))]\n",
    "        for i in range(1, len(array)):\n",
    "            left_min[i] = min(array[i], left_min[i - 1])\n",
    "            left_max[i] = max(array[i], left_max[i - 1])\n",
    "\n",
    "        right_min = [array[-1] for _ in range(len(array))]\n",
    "        right_max = [array[-1] for _ in range(len(array))]\n",
    "        for i in range(len(array) - 2, -1, -1):\n",
    "            right_min[i] = min(array[i], right_min[i + 1])\n",
    "            right_max[i] = max(array[i], right_max[i + 1])\n",
    "\n",
    "        left = -1\n",
    "        while left < len(array) - 2:\n",
    "            if (left == -1 or array[left + 1] >= array[left]) \\\n",
    "                    and left_max[left + 1] <= right_min[left + 2]:\n",
    "                left += 1\n",
    "                continue\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        right = len(array)\n",
    "        while right > 1:\n",
    "            if (right == len(array) or array[right - 1] <= array[right]) \\\n",
    "                    and left_max[right - 2] <= right_min[right - 1]:\n",
    "                right -= 1\n",
    "                continue\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return [left + 1, right - 1] if left <= right else [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if sorted(array)==array:\n",
    "            return [-1,-1]\n",
    "        tmp=sorted(array)\n",
    "        ref=[]\n",
    "        for idx,num in enumerate(tmp):\n",
    "            if num!=array[idx]:\n",
    "                ref.append(idx)\n",
    "        ans1,ans2=ref[0],ref[-1]\n",
    "        return [ans1,ans2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if array==[]:\n",
    "            return [-1,-1]\n",
    "        max_list = [array[0]]\n",
    "        min_list = [array[-1]]\n",
    "        for i in range(1, len(array)):\n",
    "            if array[i] > max_list[-1]:\n",
    "                max_list.append(array[i])\n",
    "            else:\n",
    "                max_list.append(max_list[-1])\n",
    "            if array[-i - 1] < min_list[-1]:\n",
    "                min_list.append(array[-i - 1])\n",
    "            else:\n",
    "                min_list.append(min_list[-1])\n",
    "        min_list = min_list[::-1]\n",
    "        a,b=-1,-1\n",
    "        for i in range(len(array)):\n",
    "            if array[i]>min_list[i]:\n",
    "                a=i\n",
    "                break\n",
    "        for i in range(len(array)-1,-1,-1):\n",
    "            if array[i]<max_list[i]:\n",
    "                b=i\n",
    "                break\n",
    "        return [a,b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if len(array) <=2:\n",
    "            return [-1,-1]\n",
    "        tmp0 = array\n",
    "        tmp1 = sorted(array)\n",
    "        tmp2 = [index for index,val in enumerate(array) if val != tmp1[index]]\n",
    "        if len(tmp2)>0:\n",
    "            return [tmp2[0],tmp2[-1]]\n",
    "        else:\n",
    "            return [-1,-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if len(array) <=2:\n",
    "            return [-1,-1]\n",
    "        tmp1 = sorted(array)\n",
    "        tmp2 = [index for index,val in enumerate(array) if val != tmp1[index]]\n",
    "        if len(tmp2)>0:\n",
    "            return [tmp2[0],tmp2[-1]]\n",
    "        else:\n",
    "            return [-1,-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import deque\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        n = len(array)\n",
    "        if n == 0: return [-1,-1]\n",
    "        s = deque()\n",
    "        s.append(0)\n",
    "        flag = True\n",
    "        for i in range(1,n):\n",
    "            if not s: break\n",
    "            if flag and array[i] >= array[s[-1]]:\n",
    "                s.append(i)\n",
    "            else:\n",
    "                while s and array[i] < array[s[-1]]:\n",
    "                    s.pop()\n",
    "                flag = False\n",
    "        # print(\"s={}\".format(s))\n",
    "        if s: l = min(n-1, s[-1]+1)\n",
    "        else: l = 0\n",
    "\n",
    "        s.clear()\n",
    "        s.append(n-1)\n",
    "        flag = True\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if not s: break\n",
    "            if flag and array[i] <= array[s[-1]]:\n",
    "                s.append(i)\n",
    "            else:\n",
    "                while s and array[i] > array[s[-1]]:\n",
    "                    s.pop()\n",
    "                flag = False\n",
    "        if s: r = max(0,s[-1] - 1)\n",
    "        else: r = n-1\n",
    "        # print(\"n={}, l={}, r={}\".format(n,l,r))\n",
    "        if l>=r: return [-1,-1]\n",
    "        else: return [l, r]\n",
    "\n",
    "\n",
    "        \n",
    "        # def all_smaller_than_right(l, array):\n",
    "        #     n = len(array)\n",
    "        #     target = array[l]\n",
    "        #     for i in range(l+1,n):\n",
    "        #         if target > array[i]: return False\n",
    "        #     return True\n",
    "        # def all_bigger_than_left(l, array):\n",
    "        #     n = len(array)\n",
    "        #     target = array[l]\n",
    "        #     for i in range(l-1,-1,-1):\n",
    "        #         if target < array[i]: return False\n",
    "        #     return True\n",
    "        # l, r = 0, n-1\n",
    "        # while l<=r:\n",
    "        #     mid = l + (r-1)//2\n",
    "        #     if all_smaller_than_right(mid, array):\n",
    "        #         l = mid\n",
    "            \n",
    "\n",
    "\n",
    "        # n = len(array)\n",
    "        # l, r = n-1, 0\n",
    "        # flag = False\n",
    "        # for i in range(n):\n",
    "        #     target = array[i]\n",
    "        #     for j in range(i+1,n):\n",
    "        #         if target <= array[j]: continue\n",
    "        #         else: \n",
    "        #             l = min(l, i)\n",
    "        #             flag = True\n",
    "        #             break\n",
    "        #     if flag: break\n",
    "        # flag = False\n",
    "        # for i in range(n-1,-1,-1):\n",
    "        #     target = array[i]\n",
    "        #     for j in range(i-1,-1,-1):\n",
    "        #         if target >= array[j]: continue\n",
    "        #         else:\n",
    "        #             r = max(r, i)\n",
    "        #             flag = True\n",
    "        #             break\n",
    "        #     if flag: break\n",
    "        # if l == n-1 and r == 0:\n",
    "        #     return [-1,-1]\n",
    "        # return [l,r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        p=array.copy()\n",
    "        p.sort()\n",
    "        r=[]\n",
    "        for i in range(len(array)):\n",
    "            if p[i]!=array[i]: r.append(i)\n",
    "        if r: return [r[0],r[-1]]\n",
    "        else: return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        array_sort = sorted(array)\n",
    "        if array == array_sort:\n",
    "            return [-1,-1]\n",
    "        res = []\n",
    "        for i in range(len(array)):\n",
    "            if array[i] != array_sort[i]:\n",
    "                res.append(i)\n",
    "        return [res[0],res[-1]]\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if array == None or len(array) == 0 or len(array) == 1:\n",
    "            return [-1,-1]\n",
    "        m = -1\n",
    "        j = len(array)-2\n",
    "        min = array[-1]\n",
    "        while j>=0:\n",
    "            curr = array[j]\n",
    "            if curr<=min:\n",
    "                min = curr\n",
    "            else:\n",
    "                m=j\n",
    "            j-=1\n",
    "            print(j)\n",
    "        \n",
    "        n=-1\n",
    "        max = array[0]\n",
    "        i = 1\n",
    "        while i < len(array):\n",
    "            curr = array[i]\n",
    "            if curr>=max:\n",
    "                max = curr\n",
    "            else:\n",
    "                n = i\n",
    "            i+=1\n",
    "            print(i)\n",
    "        return([m,n])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if array == None or len(array) == 0 or len(array) == 1:\n",
    "            return [-1,-1]\n",
    "        m = -1\n",
    "        j = len(array)-2\n",
    "        min = array[-1]\n",
    "        while j>=0:\n",
    "            curr = array[j]\n",
    "            if curr<=min:\n",
    "                min = curr\n",
    "            else:\n",
    "                m=j\n",
    "            j-=1\n",
    "            print(j)\n",
    "        \n",
    "        n=-1\n",
    "        max = array[0]\n",
    "        i = 1\n",
    "        while i < len(array):\n",
    "            curr = array[i]\n",
    "            if curr>=max:\n",
    "                max = curr\n",
    "            else:\n",
    "                n = i\n",
    "            i+=1\n",
    "            print(i)\n",
    "        return([m,n])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        pos = [-1, -1]\n",
    "        if len(array)<=1:\n",
    "            return pos\n",
    "        right=sorted(array)\n",
    "        print(right)\n",
    "\n",
    "        for i in range(len(array)):\n",
    "            if array[i]!=right[i]:\n",
    "                pos[0]=i\n",
    "                break\n",
    "        for i in range(1,len(array)+1):\n",
    "            if array[-i]!=right[-i]:\n",
    "                pos[1]=len(array)-i\n",
    "                break\n",
    "        return pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        lens = len(array)\n",
    "        tmp = []\n",
    "        for i in range(lens):\n",
    "            while tmp and array[tmp[-1]] > array[i]:\n",
    "                tmp.pop()\n",
    "            tmp.append(i)\n",
    "        f = 0\n",
    "        for i in range(len(tmp)):\n",
    "            if tmp[i] != i:\n",
    "                f = i \n",
    "                break \n",
    "\n",
    "        s = lens-1\n",
    "        tmp = []\n",
    "        for i in range(lens-1, -1, -1):\n",
    "            while tmp and array[tmp[-1]] < array[i]:\n",
    "                tmp.pop()\n",
    "            tmp.append(i)\n",
    "\n",
    "        print(tmp)\n",
    "\n",
    "        for i in range(len(tmp)):\n",
    "            if tmp[i] + i != lens-1:\n",
    "                s = lens-1 - i\n",
    "                break \n",
    "\n",
    "        if f == 0 and s==lens-1:\n",
    "            return [-1,-1]\n",
    "        else:\n",
    "            return [f, s]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        # 先前向遍历，再后向遍历，得到可能的区间，然后遍历这个区间得到最大值和最小值，然后分别向前向后遍历。\n",
    "        # 然后都是闭区间，left,right分别是可能的m,n\n",
    "        left = len(array)\n",
    "        for i, num in enumerate(array):\n",
    "            if i != 0 and array[i] < array[i-1]:\n",
    "                left = i\n",
    "                break\n",
    "        if left == len(array):\n",
    "            return [-1,-1]\n",
    "        \n",
    "        right = -1       \n",
    "        for j in range(len(array)-1, -1, -1):\n",
    "            if j != len(array)-1 and array[j] > array[j+1]:\n",
    "                right = j \n",
    "                break\n",
    "        if right == -1:\n",
    "            return [-1,-1]\n",
    "\n",
    "        # 计算最大值和最小值\n",
    "        max_n = max(array[left:right+1])\n",
    "        min_n = min(array[left:right+1])\n",
    "        print('l,r,max,min',left,right,max_n,min_n)\n",
    "\n",
    "        left -= 1\n",
    "        right += 1\n",
    "        # 开始向左右两边扩展,最大值和最小值都会变化，然后左右两边都要扩展\n",
    "        while left >= 0 and right < len(array) and (array[left] > min_n or array[right] < max_n):\n",
    "            if array[left] > min_n:\n",
    "                max_n = max(max_n, array[left])\n",
    "                left -= 1\n",
    "            if array[right] < max_n:\n",
    "                min_n = min(min_n, array[right])\n",
    "                right += 1\n",
    "        return [left+1, right-1]\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        new_array = sorted(array)\n",
    "        ans = []\n",
    "        for i in range(len(array)):\n",
    "            if new_array[i] == array[i]:\n",
    "                continue\n",
    "            elif new_array[i] != array[i]:\n",
    "                ans.append(i)\n",
    "        return [ans[0],ans[-1]] if ans!= [] else [-1,-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if array == None or len(array) == 0 or len(array) == 1:\n",
    "            return [-1,-1]\n",
    "        m = -1\n",
    "        j = len(array)-2\n",
    "        min = array[-1]\n",
    "        while j>=0:\n",
    "            curr = array[j]\n",
    "            if curr<=min:\n",
    "                min = curr\n",
    "            else:\n",
    "                m=j\n",
    "            j-=1\n",
    "            print(j)\n",
    "        \n",
    "        n=-1\n",
    "        max = array[0]\n",
    "        i = 1\n",
    "        while i < len(array):\n",
    "            curr = array[i]\n",
    "            if curr>=max:\n",
    "                max = curr\n",
    "            else:\n",
    "                n = i\n",
    "            i+=1\n",
    "            print(i)\n",
    "        return([m,n])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        # 至少应该满足什么条件，为什么满足这个条件就是最小的，充要条件\n",
    "        l,r = -1, -1\n",
    "        cur_min_, cur_max_ = math.inf, -1*math.inf\n",
    "        i=0\n",
    "        while i <len(array):\n",
    "            if array[i] >= cur_max_:\n",
    "                cur_max_=array[i]\n",
    "            else:\n",
    "                r = i\n",
    "                print(\"r\", i, cur_max_)\n",
    "            i+=1\n",
    "        # 从右往左\n",
    "        i = len(array)-1\n",
    "        while i >=0:\n",
    "            if array[i] <= cur_min_:\n",
    "                cur_min_ = array[i]\n",
    "            else:\n",
    "                l = i\n",
    "                print(\"l\", i, cur_min_)\n",
    "            i-=1\n",
    "        return [l,r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        array1 = sorted(array)\n",
    "        n = len(array)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if array[i]!=array1[i]:\n",
    "                res.append(i)\n",
    "        return [-1, -1] if not res else [res[0], res[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        arraysort=sorted(array)\n",
    "        if array==arraysort:\n",
    "            return [-1,-1]\n",
    "        res=[] \n",
    "        k=len(array)   \n",
    "        for i in range(k):\n",
    "            if array[i]!=arraysort[i]:\n",
    "                res.append(i)\n",
    "        return [res[0],res[-1]]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        n=len(array)\n",
    "        a=sorted(array)\n",
    "        if a==array:return [-1,-1]\n",
    "        res=[]\n",
    "        for i in range(n):\n",
    "            if array[i]!=a[i]:\n",
    "                res.append(i)\n",
    "        return [min(res),max(res)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        res = []\n",
    "        n = len(array)\n",
    "        for i in range(n):\n",
    "            while len(stack)>0 and array[stack[-1]]>array[i]:\n",
    "                res.append(stack[-1])\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        if len(res)==0: return [-1, -1]\n",
    "        start = min(res)\n",
    "         \n",
    "        stack = []\n",
    "        res = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(stack)>0 and array[stack[-1]]<array[i]:\n",
    "                res.append(stack[-1])\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        end = max(res)\n",
    "             \n",
    "        return [start, end]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if not array or len(array)<2:\n",
    "            return [-1,-1]\n",
    "        a=sorted(array)\n",
    "        r=0\n",
    "        list1=[]\n",
    "        while r<len(a):\n",
    "            if array[r]!=a[r]:\n",
    "                list1.append(r)\n",
    "            r+=1\n",
    "        if len(list1)==0:return [-1,-1]\n",
    "        else:\n",
    "            res=[]\n",
    "            res.append(list1[0])\n",
    "            res.append(list1[-1])\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        new_list = sorted(array)\n",
    "\n",
    "        if new_list == array:\n",
    "            return [-1,-1]\n",
    "\n",
    "        list_substracting = list(map(lambda x,y: x-y, new_list, array))\n",
    "        for x in range(0,len(list_substracting)):\n",
    "            if list_substracting[x] != 0:\n",
    "                first_index = x\n",
    "                break\n",
    "\n",
    "        for y in range(len(list_substracting)-1,-1,-1):\n",
    "            if list_substracting[y] != 0:\n",
    "                last_index = y\n",
    "                break\n",
    "\n",
    "        return [first_index,last_index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        res = [-1, -1]\n",
    "        b = sorted(array)\n",
    "        tmp = [array[i]-b[i] for i in range(len(array))]\n",
    "        for i in range(len(array)):\n",
    "            if tmp[i] != 0:\n",
    "                res[0] = i\n",
    "                break\n",
    "        for i in range(len(array)-1, 0, -1):\n",
    "            if tmp[i] != 0:\n",
    "                res[1] =i\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        tmp=[]\n",
    "        for i in array:\n",
    "            tmp.append(i)\n",
    "        tmp.sort()\n",
    "        res=[]\n",
    "        for i in range(len(array)):\n",
    "            if tmp[i]!=array[i]:\n",
    "                res.append(i)\n",
    "        if not res:\n",
    "            return [-1,-1]\n",
    "        return [res[0],res[-1]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        size = len(array)\n",
    "        if size <= 1 : return [-1,-1]\n",
    "        arr = filter(lambda x:x >= 0,[-1 if v==0 else i for i,v in enumerate([0 if z[0] == z[1] else 1 for z in zip(array,sorted(array))])])\n",
    "        arr = list(arr)\n",
    "        return [arr[0],arr[-1]] if len(arr) > 0 else [-1,-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        b = sorted(array)\n",
    "        if array ==b:\n",
    "            return [-1, -1]\n",
    "\n",
    "        c = list(map(lambda x, y: x - y, array, b))\n",
    "        res = [-1, -1]\n",
    "\n",
    "        for i, n in enumerate(c):\n",
    "            if res[0] == -1 and n:\n",
    "                res[0] = i\n",
    "        \n",
    "        c.reverse()\n",
    "        for i, n in enumerate(c):\n",
    "            if res[1] == -1 and n:\n",
    "                res[1] = len(c) - 1 - i\n",
    "        \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if len(array) <= 1:\n",
    "            return [-1,-1]\n",
    "        leftmax = []\n",
    "        rightmin = []\n",
    "        maxs = min(array)-1\n",
    "        for i in range(len(array)):\n",
    "            leftmax.append(maxs)\n",
    "            maxs = max(maxs,array[i])\n",
    "\n",
    "        mins = max(array)+1\n",
    "        for i in range(1,len(array)+1):\n",
    "            rightmin.append(mins)\n",
    "            mins = min(mins,array[-i])\n",
    "        rightmin = rightmin[::-1]\n",
    "        i = 0\n",
    "        m, n = -1, -1\n",
    "        print(leftmax,rightmin)\n",
    "        while i < len(array):\n",
    "            if leftmax[i] > array[i]:\n",
    "                n = i\n",
    "            i += 1\n",
    "\n",
    "        i = len(array)-1\n",
    "        while i >= 0:\n",
    "            if rightmin[i] < array[i]:\n",
    "                m = i\n",
    "            i -= 1\n",
    "        if -1 in [m,n]:\n",
    "            return [-1,-1]\n",
    "        return [m,n]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        oringal_array=array[::1]\n",
    "        array.sort()\n",
    "        n=len(array)\n",
    "        res=[]\n",
    "        for i in range(n):\n",
    "            if oringal_array[i]!=array[i]:\n",
    "                res.append(i)\n",
    "        return [res[0],res[-1]] if res else [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        a = sorted(array)\n",
    "        res = []\n",
    "        if a==array:return [-1,-1]\n",
    "        for i in range(len(array)):\n",
    "            if array[i]!=a[i]:\n",
    "                res.append(i)\n",
    "        ans = [res[0],res[-1]]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        length = len(array)\n",
    "        if not length:\n",
    "            return [-1,-1]\n",
    "        min_array = [array[0]]\n",
    "        min_array_flag = [True]\n",
    "        for i in range(1,len(array)):\n",
    "            tmp = max(array[i],min_array[-1])\n",
    "            min_array.append(tmp)\n",
    "            min_array_flag.append(tmp==array[i])\n",
    "        max_array = [array[-1]]\n",
    "        max_array_flag = [True]\n",
    "        for i in range(len(array)-2,-1,-1):\n",
    "            tmp=min(array[i],max_array[-1])\n",
    "            max_array.append(tmp)\n",
    "            max_array_flag.append(array[i]==tmp)\n",
    "        max_array = max_array[::-1]\n",
    "        max_array_flag = max_array_flag[::-1]\n",
    "        if False not in min_array_flag:\n",
    "            return [-1,-1]\n",
    "        else:\n",
    "            return [min(min_array_flag.index(False),max_array_flag.index(False)),max(length-min_array_flag[::-1].index(False)-1,length - max_array_flag[::-1].index(False)-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        a=array[:]\n",
    "        a.sort()\n",
    "        i=0\n",
    "        j=0\n",
    "        if a==array:\n",
    "            return [-1,-1]\n",
    "        for i in range(len(a)):\n",
    "            if a[i]!=array[i]:\n",
    "                break\n",
    "        for j in sorted(range(len(a)),reverse=True):\n",
    "            if a[j]!=array[j]:\n",
    "                break        \n",
    "        return [i,j]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_right_small(self,array):\n",
    "        first_small = [-1]\n",
    "        stack = []\n",
    "        for i in range(len(array)):\n",
    "            first_small.append(-1)\n",
    "            while len(stack) and array[stack[-1]] > array[i]:\n",
    "                j = stack.pop()\n",
    "                first_small[j] = i\n",
    "            stack.append(i)\n",
    "        return first_small\n",
    "\n",
    "    def get_left_big(self,array):\n",
    "        first_big = []\n",
    "        stack = []\n",
    "        for i in range(len(array)):\n",
    "            first_big.append(-1)\n",
    "            while len(stack) and array[stack[-1]] < array[i]:\n",
    "                stack.pop()\n",
    "            if len(stack):\n",
    "                if array[stack[-1]] == array[i]:\n",
    "                    first_big[i] = first_big[stack[-1]]\n",
    "                else:\n",
    "                    first_big[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        return first_big\n",
    "\n",
    "    def subSort(self,array: List[int]) -> List[int]:\n",
    "        first_small = self.get_right_small(array)\n",
    "        first_big = self.get_left_big(array)\n",
    "        min_left = -1\n",
    "        for i in range(len(array) - 1):\n",
    "            if first_small[i] != -1:\n",
    "                min_left = i\n",
    "                break\n",
    "        if min_left == -1:\n",
    "            return [-1, -1]\n",
    "\n",
    "        max_right = -1\n",
    "        for i in range(len(array) - 1, 0, -1):\n",
    "            if first_big[i] != -1:\n",
    "                max_right = i\n",
    "                break\n",
    "        return [min_left, max_right]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        minTop = [i for i in array]\n",
    "        heapq.heapify(minTop)\n",
    "        maxTop = [-i for i in array]\n",
    "        heapq.heapify(maxTop)\n",
    "        i = 0\n",
    "        j = len(array) -1\n",
    "        while j> i:\n",
    "            if array[i] == minTop[0]:\n",
    "                i+=1\n",
    "                heapq.heappop(minTop)\n",
    "            elif array[j] == -maxTop[0]:\n",
    "                j-=1\n",
    "                heapq.heappop(maxTop)\n",
    "            else:\n",
    "                return [i,j]\n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if array == []:\n",
    "            return [-1, -1]\n",
    "        n = len(array)\n",
    "        array = [-inf] + array + [inf]\n",
    "        mn = inf\n",
    "        mx = -inf\n",
    "        right = 0\n",
    "        left = n+1\n",
    "        for i in range(1, n+1):\n",
    "            if array[i] > mx:\n",
    "                mx = array[i]\n",
    "               \n",
    "            if array[i] < mx:\n",
    "                right = i\n",
    "\n",
    "        for i in range(n, -1, -1):\n",
    "            if array[i] < mn:\n",
    "                mn = array[i]\n",
    "               \n",
    "            if array[i] > mn:\n",
    "                left = i\n",
    "        print(array, left, right)\n",
    "        return [left-1, right-1] if right >= left else [-1,-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "        if len(array)==0 or len(array)==1:\n",
    "            return [-1, -1]\n",
    "\n",
    "        X = array.copy()\n",
    "        array.sort()\n",
    "        Y = [X[t]-array[t] for t in range(len(array))]\n",
    "\n",
    "        i = 0\n",
    "        j = len(array) - 1\n",
    "        while i <= j:\n",
    "            if Y[i] == 0:\n",
    "                i = i + 1\n",
    "            else:\n",
    "                break\n",
    "        i = i-1\n",
    "\n",
    "        while j > i:\n",
    "            if Y[j] == 0:\n",
    "                j = j - 1\n",
    "            else:\n",
    "                break\n",
    "        if i==j:\n",
    "            return [-1, -1]\n",
    "        else:\n",
    "            return [i+1, j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def subSort(self, array: List[int]) -> List[int]:\n",
    "\n",
    "        sort_array = sorted(array)\n",
    "        result = []\n",
    "        for i in range(len(array)):\n",
    "            if sort_array[i] != array[i]:\n",
    "                result.append(i)\n",
    "        if result != []:\n",
    "            return [result[0],result[-1]]\n",
    "        else:\n",
    "            return [-1,-1]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
